//
// Created by yangchao on 2022/5/13.
// 79. 单词搜索: https://leetcode.cn/problems/word-search/
//
#include <vector>
#include <string>
using namespace std;

class Exist{
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<pair<int,int>> directions{{-1,0},{0,-1},{0,1},{1,0}};
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m,vector<bool>(n));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(0,i,j,visited,directions,board,word)) return true;
            }
        }
        return false;
    }

    bool dfs(int index, int x, int y, vector<vector<bool>>& visited,
             vector<pair<int,int>>& directions,vector<vector<char>>& board, string word) {
        if (index == word.size()-1) return board[x][y] == word[index];
        if (board[x][y] == word[index]) {
            visited[x][y] = true;
            for (const auto& dir:directions) {
                int newX = x + dir.first, newY = y + dir.second;
                if (newX >= 0 && newX < board.size() && newY >= 0 && newY < board[0].size()) {
                    if (!visited[newX][newY]) {
                        if (dfs(index+1,newX,newY,visited,directions,board,word)) return true;
                    }
                }
            }
            visited[x][y] = false;
        }
        return false;
    }
};

